import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86183
 */
public class MySingleList implements IList{
    //  内部类
    static class ListNode{
        public int val;
        public ListNode next;//初始值为null
        //构造方法
        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;
    //创造节点
    public void createList(){
        ListNode node1 = new ListNode(6);
        ListNode node2 = new ListNode(7);
        ListNode node3 = new ListNode(2);
        ListNode node4 = new ListNode(16);
        ListNode node5 = new ListNode(20);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        this.head = node1;
    }
    //头插法
    @Override
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        node.next = head;
        head = node;

    }
//尾插法
    @Override
    public void addLast(int data) {
    ListNode node  = new ListNode(data);//一个新节点
    ListNode cur = head;
    if(head == null){//一个节点都没有时
        head = node;
        return;
    }
    while( cur.next != null){//判断cur指向  结点的下一个节点  是否为空
        cur = cur.next;
    }
    cur.next =node;
    }

    //任意位置插入法（第一个数据节点下标节点为0）
    //规则： 所有的插入，优先绑定后边
    @Override
    public void addIndex(int index, int data) {
        ListNode node =new ListNode(data);
        ListNode cur = head;
        int len = size();
        if( index < 0 || index > len){//判断index是否超出范围
            System.out.println("超出范围");
            return;
        }
        if( index == 0){//index为0 使用头插法
            addFirst(data);
            return;
        }
        if( index == len ){//len 为 len 使用尾插法
            addLast(data);
            return;
        }
        //中间插入
        while (index-1 != 0){//为了使cur指向要 插入位置的 前面的节点
            cur = cur.next;
            index--;
        }
        node.next = cur.next;//将cur指向下一个节点的位置 赋给 node要指向的下一的节点
        cur.next = node;//将node的节点 赋给 cur指向的下一个节点
    }
//查找关键字为key的节点
    @Override
    public boolean contains(int key) {
        ListNode cur = head;
        while(cur != null){
            if(cur.val == key){
                System.out.println("找到了" +"  "+ cur.val);
                return true;
            }
            cur = cur.next;
        }
        System.out.println("没找到" );
        return false;
    }
    //删除第一次关键字为key的节点
    /* //方法一
    public void remove(int key) {
        //特殊情况
        if( head == null){//空链表
            return;
        }
        if(head.val == key){
            head = head.next;
            return;
        }
        ListNode cur = head;
        while( cur.next != null){
            if(cur.next.val == key){
                cur.next = cur.next.next;
                return;
            }
            cur = cur.next;
        }
        return;
    }*/
    @Override
    //方法二
    public void remove(int key) {
        //特殊情况
        if( head == null){//空链表
            return;
        }
        if(head.val == key){
            head = head.next;
            return;
        }
        ListNode cur = findNodeOfKey(key);
        if( cur == null){
            return;
        }
        //等同于 cur.next = cur.next.next;
        ListNode del = cur.next;
        cur.next = del.next;
    }
    private ListNode findNodeOfKey(int key){
        ListNode cur = head;
        while (cur.next != null){
            if(cur.next.val == key){//cur指向下一个节点的值 是否等于  key
                return cur;//找到了，返回cur
            }
            cur = cur.next;
        }
        return null;//没有找到
    }
    //删除所有为key值的节点
    @Override
    public void removeAllKey(int key) {
        ListNode cur = head.next;
        ListNode prev = head;
        if( head == null){//空链表
            return;
        }
        while (cur != null){
            if( cur.val == key){
               prev.next = cur.next;
               cur = cur.next;
            }else{
                prev = cur;
                cur = cur.next;
            }
        }
        //放到最后面，防止出错
        if( head.val == key){
            head = head.next;
        }
    }
//获取链表长度
    @Override
    public int size() {
        int len = 0;
        ListNode cur = head;//创建一个局部变量cur
        while(cur != null){//cur 指向最后一个节点，会运算的（判断指向 节点 是否为null）
            len ++;
            cur = cur.next;//指向下一个节点
        }
        return len;
    }
    //清空所有节点
    @Override
    public void clear() {
        ListNode cur = head;
        while ( cur != null ){
            ListNode curN = cur.next;//curN 指向 cur的下一个节点
            cur.next = null;//cur不指向任何一个节点（表示存储下一个节点的地址为null）
            cur = curN;
        }
        head = null;
    }
//打印链表
    @Override
    public void display() {
        ListNode cur  = head;
        while(cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
    public boolean chkPalindrome() {
        // write code here
        ListNode fast = head;
        ListNode slow = head;
        //找中间节点  （fast走 2 步，slow走 1 步）
        while (fast != null && fast.next != null){
            //fast == null-- 奇数条件    fast.next == null -- 偶数条件
            fast = fast.next.next;
            slow= slow.next;
        }
        //翻转
        ListNode cur = slow.next;
        ListNode curN= cur;
        while ( cur != null){
            curN = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curN;
        }
        //回文（从两端开始遍历链表）
        while (head != slow ){
            if (slow.val != head.val){
                return false;
            }
            //前提 slow.val == head.val 时，判断head 下一个节点 是否 等于 slow节点
            if (head.next == slow){
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return  true;
    }
}
